//牛客：01背包模板
#include <iostream>
#include <vector>
using namespace std;
void Solution1(vector<vector<int>>& nums, int V) {
    //1、创建dp表
    int m = nums.size();
    vector<int> dp(V+1);
    //2、填表
    for (int i = 1 ; i <= m ; ++i) {
        for (int j = V ; j >= 0 ; --j) {
            int v = nums[i - 1][0], w = nums[i - 1][1];
            if (j - v >= 0) {
                dp[j] = max(w + dp[j - v], dp[j]);
            } ;
        }
    }
    //3、返回值
    cout << dp[V] << endl;
}
void Solution2(vector<vector<int>>& nums, int V) {
    //1、创建dp表
    int m = nums.size();
    vector<int> dp(V + 1);
    //2、初始化
    for (size_t i = 1 ; i <= V ; ++i)
        dp[i] = -1;
 
    //3、填表
    for (int i = 1 ; i <= m ; ++i) {
        for (int j = V ; j >= 0 ; --j) {
            int w = nums[i - 1][1], v = nums[i - 1][0];
            if (j - v >= 0 && dp[j - v] != -1 && w + dp[j - v] > dp[j])
                dp[j] = w + dp[j - v];
        }
    }
    //4、返回值
    if (dp[V] == -1) cout << 0 << endl;
    else cout << dp[V] << endl;
}
 
int main() {
    int n, V;
    cin >> n >> V;
    vector<vector<int>> nums(n, vector<int>(2));
    for (auto& v : nums)
        for (auto& x : v)
            cin >> x;
 
    Solution1(nums, V);
    Solution2(nums, V);
    return 0;
}

//分割等和子集
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto& x : nums) sum += x;

        int target = sum / 2 , n = nums.size();
        if(sum % 2 == 1) return false;
        vector<bool> dp(target+1);
        for(size_t i = 0 ; i <= n ; ++i) dp[0] = true;

        for(int i = 1 ; i <= n ; ++i)
            for(int j = target ; j >= 0 ; --j)
                dp[j] = dp[j] || (j-nums[i-1] >= 0 && dp[j-nums[i-1]]);

        return dp[target];
    }
};

//目标和
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(auto& x : nums) sum += x;
        int a = (sum + target)/2;
        if(a < 0 || (sum + target)%2) return 0;
        int m = nums.size();cout << a << endl;
        vector<vector<int>> dp(m+1,vector<int>(a+1));
        dp[0][0] = 1;
        for(int i = 1 ; i <= m ; ++i)
        {
            for(int j = 0 ; j <= a ; ++j)
            {
                dp[i][j] = dp[i-1][j];
                if(j - nums[i-1] >= 0) dp[i][j] += dp[i-1][j-nums[i-1]];
            }
        }
        return dp[m][a];
    }
};